Programmable logic devices (PLDs) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (FPGA), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (IOBs), slices, look-up tables (“LUTs”), configurable logic blocks (CLBs), dedicated random access memory blocks (BRAM), multipliers, digital signal processing blocks (DSPs), processors, clock managers, delay lock loops (DLLs), and so forth.
Each programmable tile typically includes both programmable interconnect and programmable logic. The programmable interconnect typically includes a large number of interconnect lines of varying lengths interconnected by programmable interconnect points (PIPs). The programmable logic implements the logic of a user design using programmable elements that can include, for example, function generators, registers, arithmetic logic, and so forth.
The programmable interconnect and programmable logic are typically programmed by loading a stream of configuration data into internal configuration memory cells that define how the programmable elements are configured. The configuration data can be read from memory (e.g., from an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
Assigning a hardware unit of an FPGA and configuring it to perform the desired function for a specific circuit component (i.e., a component of the circuit that the FPGA is configured to operate as) is referred to as “placing” the component. The process of assigning and configuring hardware units on an FPGA to all the components in a circuit is called “placement”. The term “site” is used to describe the physical location on an FPGA where a circuit component is implemented on the FPGA.
ICs are designed using computers programmed with electronic design automation (“EDA”) and electronic computer-aided design (“EGAD”) tools. These tools are used to provide both logical and physical synthesis. EDA tools take an abstract representation of a circuit design and transform it into an arrangement of logic or other structures connected to one another as described in a network list (“netlist”). The netlist is provided to a synthesis tool that directs a placer of a place-and-route tool. The synthesis tool drives the placer according to standard conventions and design-, device-, or user-specific constraints. In other words, the placer is a software tool that performs the task of placing circuit components to specific physical sites of an FPGA in order to implement a circuit design (application) on the FPGA.
In one example, a placer implements a circuit on an FPGA in two phases. First, the placer distributes all the components into areas of an FPGA design (i.e., a software representation of a physical FPGA chip), which is called “spreading”. Second, the placer assigns specific sites of the FPGA to each circuit component in an operation called “fitting”.
The way a placer decides on spreading a component into a chip area or fitting it on a site is derived by considering many aspects of the circuit and the chip, such as whether the site can be configured to perform the function of the component, the distances between the component and other components that it will be connected to, and whether the site is already used by another component.
A component might not require all the resources of a site and placing the component at that site would not fully utilize the resources of the FPGA chip. The way in which a conventional placer assigns a component to a site becomes difficult when the number of components is close to the number of available sites.
A placement tool uses algorithms that find legal locations for all the components of a design on the IC chip. Unfortunately, conventional placement tools typically produce solutions that do not guarantee that components do not share device resources. Resource sharing is commonly known as overlap or over-subscription. Over-subscription degrades the quality of the overall placement and final placement solutions because downstream algorithms in the placement flow work off of the overall placement solution.
It is desirable to place components of a circuit implemented in an FPGA in a manner that avoids the problems of the prior art.